介紹完資料結構，總算進入到演算法的部分，根據課綱，我們首先從排序演算法(sorting algorithm)開始看:
排序演算法將資料由小到大(ascending)或由大到小(descending)排序，其有兩種分類方式，space used(空間使用，排序時是否需要額外的空間)或是stability(直翻為穩定度，其實就是排序時同類型元素的順序是否改變)。

• 1. 空間使用 (space used)
     a. In place sorting: 排序演算法排序時不需要額外的空間。e.g. Bubble Sort
     b. Out of place: 排序演算法排序時需要額外的空間。e.g. Merge Sort
• 2. 穩定度 (stability) (圖1)
     a. Stable sorting: 類似的元素在重新排列後未改變其順序 e.g. Insertion Sort
     b. Unstable sorting: 反之，類似的元素在重新排列後改變其順序 E.g. Quick sort

圖1 從圖1可以看到，如果是stable sorting的話，藍色40和黃色40的相對位子沒有改變(黃前藍後)，但如我是unstable sorting，相對位子就改了。

氣泡排序法(Bubble Sort)

那首先，我們先來看沒有效率但赫赫有名的氣泡排序法(Bubble sort)，氣泡排序法就是不斷重複比較相鄰兩個值，若順序不對，交換順序，直到所有數值排序正確。寫起來簡單且空間複雜度低(O(1))但其缺點是其時間複雜度差O(n^2)。

# 由小到到大排(ascending)
# 時間複雜度: O(n^2), 空間複雜度: O(1)
def BubbleSort(mylist):
    for j in range(len(mylist)-1):
        for i in range(len(mylist)-1):
            if mylist[i] > mylist[i+1]:
                mylist[i], mylist[i+1] = mylist[i+1], mylist[i]
    return mylist

mylist = [10, 9, 20, 2, 16, 8]
print(BubbleSort(mylist))
>> [2, 8, 9, 10, 16, 20]

選擇排序法(Selection Sort)

Selection Sort (選擇排序法): 將陣列分成排序和未排序的部分，以由小排到大的例子來說，在未排序的持續找最小值(若為由小到大的排序是這樣)，並將之交換到左邊已排序的部分。寫起來簡單且空間複雜度低(O(1))，但缺點也是時間複雜度差O(n^2)。

def SelectionSort(mylist):
    for i in range(len(mylist)):
        minvalue=mylist[i]
        # 從i+1開始，就是沒有排序的，從沒排序的序列找最小值
        for j in range(i+1,len(mylist)):
            if mylist[j]<minvalue:
                minvalue=mylist[j]
        mylist[mylist.index(minvalue)],mylist[i]=mylist[i],mylist[mylist.index(minvalue)]
    return mylist
      
mylist=[10,9,20,2,16,8]
print(SelectionSort(mylist))
>> [2, 8, 9, 10, 16, 20]

插入排序法(Insertion Sort)

插入排序法將陣列分成未排序與排序的部分，將元素一個個由未排列的部分拿到已排列的部分並在已排列的部分排序，直到未排列的陣列為空。優缺點跟前面幾個排序一樣，低空間複雜度(O(1))，高時間複雜度O(n^2)。

def InsertionSort(mylist):
    for i in range(len(mylist)):
        key=mylist[i]
        j=i-1
        while j>=0 and key<mylist[j]:
            mylist[j+1]=mylist[j]
            j-=1
        mylist[j+1]=key
    return mylist

mylist=[10,9,20,2,16,8]
print(InsertionSort(mylist))
>> [2, 8, 9, 10, 16, 20]

圖2 為氣泡排序法、選擇排序法、插入排序法式意圖。

桶排序法(Bucket Sort)

Bucket Sort (桶排序法): 創建幾個小陣列(桶)將資料分別裝至其中，將每桶分別用insertion sort或是selection sort這種適合少量資料的排序法排序，最後將以排序的小桶們按順序合併。此方法平均時間複雜度O(nlogn)雖然較上述方法快，但其空間複雜度為O(n)，當記憶體空間為重要考量時不適合。(圖3，看圖感覺比較好理解)

圖3，排序法示意圖。

import math

# 需要用到前面寫的insertion sort為小桶們排序
def insertionSort(mylist):
    for i in range(1, len(mylist)):
        key = mylist[i]
        j = i-1
        while j >= 0 and key < mylist[j]:
            mylist[j+1] = mylist[j]
            j = j-1
        mylist[j+1] = key
    return mylist


def BucketSort(mylist):
    # 要分配桶子，還有總共要多少桶
    numberofbucket = round(math.sqrt(len(mylist)))
    maxValue = max(mylist)
    arr = []
    for i in range(numberofbucket):
        arr.append([])
    for j in mylist:
        index = math.ceil(j*numberofbucket/maxValue)
        arr[index-1].append(j)
    # 為每一小桶做排序
    for i in range(numberofbucket):
        arr[i] = insertionSort(arr[i])
    k = 0
    # 再整合所有桶子
    for i in range(numberofbucket):
        if arr[i] == None:
            pass
        else:
            for j in range(len(arr[i])):
                mylist[k] = arr[i][j]
                k += 1
    return mylist


mylist = [10, 9, 20, 2, 16, 8, 90, 80, 50, 60, 73, 26, 46]
print(BucketSort(mylist))
>> [2, 8, 9, 10, 16, 20, 26, 46, 50, 60, 73, 80, 90]

參考資料:
The Complete Data Structures and Algorithms Course in Python (udemy) 有興趣可以自己上去看